The related art will be described below.
Inventors including part of the present inventors have already proposed a database system to cope with information leakage (see, for example, Patent Literature 1). FIG. 1 is an explanatory diagram newly created by the present inventors in order to exemplify an outline of one aspect of the disclosure of Patent Literature 1. The following describes the outline. Note that in FIG. 1, names and reference numerals of constituent elements are not the same as those in the drawings of Patent Literature 1.
An application apparatus 110 on which an application software (program) runs issues a request to perform a certain process on data stored (stored with being encrypted) in a database system 130 and send back to the application apparatus 110. An intermediate apparatus (corresponds to a user system in Patent Literature 1) 120 changes this request adapted to a method for applying a cryptographic protocol in the database and an application result of the method (query sentence 1) and sends the query sentence 1 to the database system 130. The result of this request is, for example, a ciphertext. There are cases in which simple decryption of the ciphertext does not provide processed data requested by the application apparatus 110.
In response to the request from the intermediate apparatus 120, the database control means 131 processes the data in ciphertext by using the encryption protocol 133 and sends the processed result to the intermediate apparatus 120. The intermediate apparatus 120 decrypts received data, applies further processing (corresponding to a query sentence 2) as necessary, and then sends the data to the application apparatus 110.
Since a cyphertext is processed using the cryptographic protocol 133 in the database system 130, the ciphertext of data requested by the application apparatus 110 cannot always be generated promptly. Further, there are sometimes such cases wherein the database control means 131 can reduce data amount (transfer amount) to be returned to the intermediate apparatus 120, by filtering data in ciphertext as it is or by calculating statistical values in ciphertext as it is. Furthermore, when the intermediate apparatus 120 is adapted to process a plaintext obtained by decrypting the encrypted data using a secret key 121, the intermediate apparatus 120 can perform such data processing that could not be performed on data in ciphertext as it is. As a result, data desired by the application apparatus 110 can be sent to the application apparatus 110.
With such a technique, when the application apparatus 110 issues a request for data to the database system 130, as though the data is not encrypted, the database system 130 can deliver desired data to the application apparatus 110, even when the data that has been encrypted is stored and the database 130 has not an encryption key. In addition, the amount of data transferred from the database system 130 to the intermediate apparatus 120 can be reduced as compared with a case of passing all ciphertexts related to the request.
Secret sharing schemes are widely known as information security technologies (reference may be made to Non-Patent Literatures 1 and 2). For example, it is possible to implement a system that distributes information to a plurality of databases or memory systems by using secret sharing scheme to reduce possibility of occurrence of loss of original information, due to possibility of information leakage and data corruption etc.
A (k, n) threshold secret sharing scheme by polynomial interpolation includes the following distribution and reconstruction processing (reference may be done to Non-Patent Literatures 1 and 2, etc.).
<Distribution>
A random k−1 order polynomial with a secret s as a constant term a0 F(x)=a0+a1·x+a2·x{circumflex over ( )}(k−1)(a1 to ak−1 are integers, {circumflex over ( )} is a power operator). An owner of the secret s sends F(i) as a share Wi to a share holder (apparatus) with an identifier i. It is assumed that identifiers 1 to n are allocated to n share holders.<Reconstruction>
The secret s (=a0) can be obtained by collecting (i, Wi) of k share holders.
When realizing the (k, n) threshold scheme on finite prime field Z/qZ with q as a prime, the coefficients a0 to ak−1 of the polynomial are also an element on Z/qZ and addition, subtraction, and multiplication, are performed on Z/qZ. The secret s (=F (0)) is also an element on Z/qZ. The share of the share holder i is F(i) mod q. The secret s (=F(0) mod q), obtained by selecting a set S={i1, . . . , ik}⊂{1, 2, . . . , n}, using Lagrangian interpolation. F (0) is given by:
                              F          ⁡                      (            0            )                          =                ⁢                              ∑                                          i                I                            ∈              S                                ⁢                                    F              ⁡                              (                                  i                  I                                )                                      ⁢                                          λ                                                      i                    I                                    ,                  s                                            ⁡                              (                0                )                                      ⁢            mod            ⁢                                                  ⁢            q                                                  =                ⁢                              ∑                                          i                I                            ∈              S                                ⁢                                    F              ⁡                              (                                  i                  I                                )                                      ⁢                                          ∏                                                      i                    j                                    ∈                                      S                    ⁢                    \                    ⁢                                          i                      I                                                                                  ⁢                                                          ⁢                                                                    -                                          i                      j                                                                                                  i                      I                                        -                                          i                      j                                                                      ⁢                mod                ⁢                                                                  ⁢                q                                                        
In realizing the (k, n) threshold secret sharing scheme on the finite prime field Z/qZ, even if k−1 shares are collected, information on secret s cannot be obtained at all.
There is known a (K, L, n) threshold ramp type secret sharing scheme using three parameter that allows some information of secret s to be obtained from 1 share (k−L+1≤1≤k−1), but it is possible to obtain information of the secret s from k shares (k is a threshold) and information on the secret s cannot be obtained at all from k−L shares (for example, reference may be made to Non-Patent Literature 2).
That data A is secrete-shared means that each of a plurality of shares obtained by secret sharing of the data A is held in each of the apparatus sets.
In a secure multiparty computation, secret-shares of data are sent to a plurality of apparatuses which repeatedly perform partial calculation of secret shares, so that various calculations can be performed with the data being kept concealed.
For example, in the multi-party protocol, each apparatus i (i=1 to n) distributes shares w1i, . . . , wii, . . . , wni obtained by secret sharing of the secret si of the apparatus to each apparatus. Each apparatus i (i=1 to n) holds the shares wi1, . . . , wii−1, wii+1, . . . , win distributed to the apparatus i from other apparatuses j (j=1 to n, where j≠i) in addition to the share wi and calculates the function h (w11, w21, . . . , w1i, w2i, . . . , wnn)=(v1, . . . , vi, . . . , vn), where v1, . . . , vi, . . . vn are shares of function values v=g (s1, s2, . . . , sn) of the secret information s1, s2, . . . , sn (see Non-Non-Patent Literature 3). Non-Non-Patent Literature 3 proposes an arrangement that enables execution of relational algebra operations using multi-party protocols and enables all structural operations without decrypting data on a database distributed by a secret sharing scheme.
To generate secret shared data B by performing secure computation on secret shared data A, means that the secure computation starts from a state where the data A is secret shared and ends with a state wherein the data B is secret shared. In the multi-party protocol, each participant has secret information, and a function of the secret information is calculated with the secret information kept concealed.
As mentioned above, when certain data is secret-shared, the original data can be reconstructed by collecting a certain number of shares. Or, even if the same share as the share that can be obtained by secret sharing of certain data is generated in some way, it is possible to reconstruct the corresponding data by collecting a certain number of these shares.